POI2013 Bytecomputer

POI
dp

POI2013 Bytecomputer

题目大意:

给定一个{-1,0,1}组成的序列,你可以进行$x[i]=x[i]+x[i-1]$这样的操作,求最少操作次数使其变成不降序列。

题解：

首先猜测，从左往右依次过来，一定能够得到一组最优解。(哪位大神会证来教教我)

于是定义dp[i][j]表示到i为止，结尾为j的最小代价。

$O(n)​$ 暴力转移即可。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
void Rd(int&res){
	res=0;char c;int k=1;
	while(c=getchar(),!isdigit(c)&&c!='-');
	if(c=='-')k=-1,c=getchar();
	do res=res*10+(c&15);
		while(c=getchar(),isdigit(c));
	res=res*k;
}
const int N=1000005,inf=1<<30;
int n,num[N],dp[3][N];
int main(){
	Rd(n);
	for(int i=1;i<=n;i++)Rd(num[i]);
	if(num[1]==-1)dp[0][1]=0,dp[1][1]=dp[2][1]=inf;
	else if(num[1]==0)dp[1][1]=0,dp[0][1]=dp[2][1]=inf;
	else dp[2][1]=0,dp[0][1]=dp[1][1]=inf;
	for(int i=2;i<=n;i++){
		if(num[i]==1){
			dp[2][i]=min(dp[0][i-1],min(dp[1][i-1],dp[2][i-1]));
			dp[1][i]=dp[0][i-1]+1;
			dp[0][i]=dp[0][i-1]+2;
		}else if(num[i]==-1){
			dp[2][i]=dp[2][i-1]+2;
			dp[1][i]=inf;
			dp[0][i]=dp[0][i-1];
		}else{
			dp[2][i]=dp[2][i-1]+1;
			dp[1][i]=min(dp[0][i-1],dp[1][i-1]);
			dp[0][i]=dp[0][i-1]+1;
		}
	}
	int ans=min(dp[0][n],min(dp[1][n],dp[2][n]));
	if(ans>=inf)printf("BRAK\n");
	else printf("%d\n",ans);
	return 0;
}
分享到 评论